import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        // s.generate(2);
        int[] c = new int[]{3,6,1,3,4};
        int[] r = new int[]{2,1,3,4,5};
        System.out.println(s.maximumRobots(c, r, 25));
    }

    public List<List<Integer>> generate(int numRows) {
        /**
         * 杨辉三角*/
        // 1 创建返回值
        List<List<Integer>> ret = new LinkedList<>();
        // -创建初始值
        List<Integer> firstRow = new LinkedList<>();
        firstRow.add(1);
        ret.add(firstRow);

        // 2 执行填表逻辑
        for(int i = 1; i < numRows; i++) {
            // -创建层级存储
            List<Integer> cur = new LinkedList<>();
            cur.add(1);
            // -循环填表
            for(int j = 1; j < i; j++) {
                cur.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
            }
            cur.add(1);
            ret.add(cur);
        }

        // 3 返回值
        return ret;
    }

    public int maximumRobots(int[] c, int[] r, long budget) {
        /**
         * 预算内的最多机器人的数目
         * 单调队列和前缀和之间的下标映射关系：left（原映射关系），right=right-1*/
        // 1 预处理
        int n = c.length;

        // 2 准备运行时间前缀和
        long[] prevSum = new long[n+1];
        for(int i = 1; i <= n; i++) {
            prevSum[i] = prevSum[i-1] + r[i-1];
        }

        // 3 准备单调队列（记录窗口内充电时间最大值，存储值为（值：下标））
        Deque<int[]> queue = new LinkedList<>();

        // 4 滑动窗口
        int left = 0;
        int right = 1;
        int maxCount = 0;
        while(right <= n) {
            // -1 进窗口（维护窗口内充电时间最大值队列）
            while(!queue.isEmpty() && queue.peekLast()[0] <= c[right-1]) {
                queue.pollLast();
            }
            queue.offerLast(new int[]{c[right-1], right-1});
            // -2 判断（判断总开销是否大于等于预算）
            while(!queue.isEmpty() && queue.peekFirst()[0] + (right-left) * (prevSum[right]-prevSum[left]) > budget) {
                // -3 出窗口（维护窗口内充电时间最大值队列）
                left ++;
                while(!queue.isEmpty() && queue.peekFirst()[1] < left) {
                    queue.pollFirst();
                }
            }
            // -4 更新值（到此处必定符合要求）
            maxCount = Math.max(right - left, maxCount);

            right ++;
        }

        // 5 返回值
        return maxCount;
    }
}

